package io.github.hadyang.leetcode.bytedance;

import org.junit.Test;

import java.util.LinkedList;

import io.github.hadyang.leetcode.TreeNode;

/**
 * 二叉树的最近公共祖先
 *
 * <p>给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *
 * <p>百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 *
 * <p>例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
 *
 * @author haoyang.shi
 */
public class Link1026 {

  @Test
  public void test() {
    TreeNode treeNode1 = new TreeNode(3);
    TreeNode treeNode2 = new TreeNode(5);
    TreeNode treeNode3 = new TreeNode(1);
    TreeNode treeNode4 = new TreeNode(6);
    TreeNode treeNode5 = new TreeNode(2);
    TreeNode treeNode6 = new TreeNode(0);
    TreeNode treeNode7 = new TreeNode(8);
    TreeNode treeNode8 = new TreeNode(7);
    TreeNode treeNode9 = new TreeNode(4);

    treeNode1.left = treeNode2;
    treeNode1.right = treeNode3;

    treeNode2.left = treeNode4;
    treeNode2.right = treeNode5;

    treeNode3.left = treeNode6;
    treeNode3.right = treeNode7;

    treeNode5.left = treeNode8;
    treeNode5.right = treeNode9;

    System.out.println(lowestCommonAncestor(treeNode1, treeNode2, treeNode3));
    System.out.println(lowestCommonAncestor(treeNode1, treeNode2, treeNode9));
  }

  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    LinkedList<TreeNode> pathP = new LinkedList<>();
    LinkedList<TreeNode> pathQ = new LinkedList<>();

    findNodePath(pathP, root, p);
    findNodePath(pathQ, root, q);

    TreeNode last = null;
    while (!pathP.isEmpty() && !pathQ.isEmpty()) {
      TreeNode pi = pathP.pollFirst();
      TreeNode qi = pathQ.pollFirst();

      if (qi == pi) {
        last = pi;
      } else break;
    }

    return last;
  }

  private void findNodePath(LinkedList<TreeNode> path, TreeNode root, TreeNode target) {
    if (root == null) {
      return;
    }

    if (!path.isEmpty() && path.getLast().val == target.val) {
      return;
    }

    path.addLast(root);

    findNodePath(path, root.left, target);
    if (!path.isEmpty() && path.getLast().val == target.val) {
      return;
    }

    findNodePath(path, root.right, target);

    if (!path.isEmpty() && path.getLast().val != target.val) {
      path.removeLast();
    }
  }
}
